#include "PriorityQueue.h"


void Swap(PriorityQueueDataType *a, PriorityQueueDataType *b)
{
    PriorityQueueDataType tmp = *a;
    *a = *b;
    *b = tmp;
}

PriorityQueue *PQ_Create(int capacity)
{
    assert(capacity > 0);
    PriorityQueue *pq = (PriorityQueue *)malloc(sizeof(PriorityQueue));
    if(pq == NULL)
    {
        fprintf(stderr, "Memory allocation failed, PQ_Create operation aborted.");
        return NULL;
    }
    pq->elements= (PriorityQueueDataType *)malloc(capacity * sizeof(PriorityQueueDataType));
    pq->capacity = capacity;
    pq->size = 0;
    return pq;
}

void PQ_Destroy(PriorityQueue *pq)
{
    assert(pq);

    pq->capacity = pq->size = 0;
    pq->elements = NULL;

    free(pq);

    pq = NULL;
    /* Note : Here, the function takes a pointer to a pointer to PriorityQueue.
     * This allows us to modify the pointer passed in from the caller's scope,
     * thus setting it to NULL to avoid dangling pointers.
     */
    // 这里释放内存，需要将函数外部也设置为NULL，否则会存在内存泄漏。
    // 当然，你可以修改参数类型为PriorityQueue **ppq, 然后在函数内部将*ppq = NULL;
    // 亦或者修改返回类型，使其return pq;来将值传递给调用者。
}

void MinHeap(PriorityQueueDataType *elements, int size)
{
    int child = size - 1;
    while(child>0)
    {
        int parent = (child - 1) / 2;
        if(elements[child]->weight<elements[parent]->weight)
        {
            Swap(elements + child, elements + parent);
            child = parent;
        }else{
            break;
        }

    }
}

void PQ_AdjustDown(PriorityQueueDataType *elements, int size)
{
    int parents = 0;
    int child = parents*2+1;
    while(child<size)
    {
        if(child+1<size && elements[child]->weight>elements[child+1]->weight)
        {
            ++child;
        }
        if(elements[parents]->weight>elements[child]->weight)
        {
            Swap(elements + parents, elements + child);
            parents = child;
            child = 2*parents+1;
        }
        else
        {
            break;
        }
    }
}
void PQ_Insert(PriorityQueue *pq, PriorityQueueDataType x)
{
    assert(pq); 

    if (PQ_IsFull(pq))
    {
        int newCapacity = pq->capacity * 2;
        // 重新分配内存给elements指针，使其大小为新的容量
        // Reallocate memory for the elements pointer with the new capacity
        PriorityQueueDataType *newElements = (PriorityQueueDataType *)realloc(pq->elements, sizeof(PriorityQueueDataType) * newCapacity);
        if(newElements == NULL)
        {
            // Output error message to the standard error stream
            fprintf(stderr, "Memory allocation failed, PQ_Insert operation aborted.\n");
            return;
        }

        // 更新队列的elements指针和capacity
        // Update the elements pointer and capacity of the queue
        pq->elements = newElements;
        pq->capacity = newCapacity;
    }

    // 在队列末尾插入元素，并调整至堆结构
    // Insert the element at the end of the queue and adjust the heap structure
    pq->elements[pq->size++] = x;
    MinHeap(pq->elements, pq->size); // 调用MinHeap函数，将新插入的元素调整为最小堆结构
}

PriorityQueueDataType PQ_Extract(PriorityQueue *pq)
{
    assert(pq);
    if(PQ_IsEmpty(pq))
    {
        fprintf(stderr, "Priority Queue is empty\n");
        PriorityQueueDataType x = {0};
        return x;
    }
    PriorityQueueDataType x = pq->elements[0];
    Swap(&pq->elements[0], &pq->elements[pq->size-1]);
    PQ_AdjustDown(pq->elements, --pq->size);
    return x;
}

bool PQ_IsEmpty(PriorityQueue *pq)
{
    assert(pq);
    return pq->size == 0;
}

int PQ_Capacity(PriorityQueue *pq)
{
    assert(pq);
    return pq->capacity;
}

bool PQ_IsFull(PriorityQueue *pq)
{
    assert(pq);
    return pq->size == pq->capacity;
}